package code1.binary_tree;

import java.util.HashMap;
import java.util.Map;

/**
 * 原题链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/
 */
public class P106 {

    //根据中序序列和后序序列构建二叉树

    //key-中序序列的值，value-中序序列的下标，便于查找
    Map<Integer,Integer> map=new HashMap<>();

    //用begin和end来表示序列范围，采用[begin,end)方式来表示
    public TreeNode findNode(int[] inorder,int inBegin,int inEnd,int[] postorder,int postBegin,int postEnd){
        if(inBegin>=inEnd || postBegin>=postEnd){   //序列为空，说明没有元素了
            return null;
        }
        Integer rootIndex = map.get(postorder[postEnd - 1]);    //找到后序序列中最后一个元素在中序序列中的下标
        TreeNode root=new TreeNode(inorder[rootIndex]);         //创建结点
        int len = rootIndex-inBegin;          //分割后的左中序子序列的长度(也就是分割后的左后序子序列的长度)
        //用分割后的左中序子序列和左后序子序列来构建左子树
        root.left=findNode(inorder,inBegin,rootIndex,postorder,postBegin,postBegin+len);
        //用分割后的右中序子序列和右后序子序列来构建右子树
        root.right=findNode(inorder,rootIndex+1,inEnd,postorder,postBegin+len,postEnd-1);
        return root;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return findNode(inorder,0,inorder.length,postorder,0, postorder.length);
    }
}
